package algorithm.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 给一个二维矩阵,每个格子中的数字代表走过这个格子的收益,现在你从左上角出发目的地是右下角,你每一步可以向右/向下/向右下三个方向选一个走一步
 * 请给出最大收益的**全部路径**
 *
 * 我当时的思路是先dp找到从左上到右下的最大收益,然后dfs全部等于最大收益的路径
 * 自创题,未验证
 */


// 1 3 2
// 2 1 2
// 3 2 2

public class Bytedance {

    public List<List<int[]>> searchRoutine(int[][] table) {
        List<List<int[]>> result = new LinkedList<>();

        // 先dp得到组大收益
        int[][] dp = new int[table.length][table[0].length];
        for (int i = 0; i < table.length; i++) {
            for (int j = 0; j < table[0].length; j++) {
                if (i == 0 && j == 0) dp[i][j] = table[i][j];
                else if (i == 0) dp[i][j] = dp[i][j-1] + table[i][j];
                else if (j == 0) dp[i][j] = dp[i-1][j] + table[i][j];
                else dp[i][j] = Math.max(dp[i-1][j-1], Math.max(dp[i-1][j], dp[i][j-1])) + table[i][j];
            }
        }

        // dfs得到全部路径
        int maxProfit = dp[table.length - 1][table[0].length - 1];
        dfs(result, new LinkedList<>(), 0, 0, maxProfit, table);
        return result;
    }

    public void dfs(List<List<int[]>> result,
                    LinkedList<int[]> temp,
                    int row,
                    int col,
                    int left,
                    int[][] table) {
        // 首先一定检查是否越界
        if (row >= 0 && row < table.length && col >= 0 && col < table[0].length) {
            temp.add(new int[]{row, col});
            // 检查是否结束
            if (row == table.length-1 && col == table[0].length-1) {
                if (left == table[row][col]) result.add(new LinkedList<>(temp));
                // 一开始我在这里加了return导致最后一个点return无法触发removeLast
                // 实际上不用手动removeLast,让程序自己越界之后自动删除
            }
            // 向三个方向探索
            else {
                dfs(result, temp, row+1, col, left-table[row][col], table);
                dfs(result, temp, row, col+1, left-table[row][col], table);
                dfs(result, temp, row+1, col+1, left-table[row][col], table);
            }
            temp.removeLast();
        }
    }

    public static void main(String[] args) {
        Bytedance bd = new Bytedance();
        int[][] table = new int[3][3];
        table[0] = new int[]{1,3,2};
        table[1] = new int[]{1,10,2};
        table[2] = new int[]{3,2,2};
        List<List<int[]>> lists = bd.searchRoutine(table);
        for (List<int[]> list : lists) {
            for (int[] ints : list) {
                System.out.print(Arrays.toString(ints));
                System.out.print(", ");
            }
            System.out.println();
        }
    }

}
